package xiaohong.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class RadixSortDemo {

    public static void main(String[] args) {
        int[] nums = new int[10000000];
        for (int i = 0; i < 10000000; i++) {
            nums[i] = (int)(Math.random() * 100000000);
        }
        Date date = new Date();
        SimpleDateFormat formatter = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println( "排序之前时间" +formatter.format(date));
        radixSort(nums);
        Date date1 = new Date();
        System.out.println( "排序之后时间" +formatter.format(date1));
    }

    public static void radixSort(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();

        int [][] buckets = new int[10][arr.length];
        int[] bucketElementCounts = new int[10];

        for (int k = 0 ,  n = 1; k < maxLength; k++ , n*=10) {
            for (int j : arr) {
                int digitOfElement = j / n % 10;
                buckets[digitOfElement][bucketElementCounts[digitOfElement]] = j;
                bucketElementCounts[digitOfElement]++;
            }
            int index = 0;

            for (int i = 0; i < bucketElementCounts.length; i++) {
                if (bucketElementCounts[i] != 0) {
                    for (int l = 0; l < bucketElementCounts[i]; l++) {
                        arr[index++] = buckets[i][l];
                    }
                    bucketElementCounts[i] = 0;
                }
            }
        }


    }



}
